(1) Field of the Invention
The present invention relates to a sequential decoder for decoding a systematic and convolutional code signal having a code rate greater than 1/2 and carrying out error correction coding of the code signal. This is achieved by determining a local most likely path in a plurality of possible paths for a newly received information bit by calculating a branch metric indicating likelihood of each of the plurality of possible paths in accordance with a predetermined algorithm.
Error correction coding is used at a receiver side for enabling correction of errors occurring during transmission of data. FIG. 1 shows the construction of an example of an encoder which receives a series of binary data consisting of information bits and generates a parity bit for each information bit. That is, the encoder of FIG. 1 generates a systematic and convolutional code signal having a code rate of 1/2. An example of coded output corresponding to an input data series "0011101" is shown in FIG. 2.
Usually, sequential decoders have an internal encoder identical to the encoder by which the transmitted signal has been encoded on the sender side. The sequential decoders sequentially decode the transmitted signal using an output of the internal encoder, and selects a local most likely value, of the transmitted signal in a trial and error method. The internal encoder generates a parity bit from information bits which are decoded in the sequential decoder.
Generally, a series of binary data can be expressed as a path consisting of a series of branches in a tree diagram as shown in FIG. 3. Therefore, the process of decoding encoded and transmitted data consists of determining a local most likely path consisting of a series of branches in a tree diagram, and locally (at each node of the tree diagram), the process of sequential decoding corresponds to determination (selection) of a local most likely branch in a plurality of branches extending forward (to the right in FIG. 3) from the node.
Calculation of the likelihood for each branch, and the determination of the local most likely path is carried out in accordance with a predetermined algorithm. The most popular algorithm is known as the Fano algorithm, which is disclosed by R. M. Fano. in "Heuristic Discussion of Probabilistic Decoding", IEEE Transaction of Information Theory, Vol. IT.19, April 1963, pp.64-73, and U.S. Pat. No. 3,457,562. As an other algorithm, the stack algorithm which was independently proposed by Z. Zigangirov ("Some Sequential Decoding Procedures", Probabl. Peredachi Inf., Vol.2, No.4, 1966, pp.13-25), and F. Jelinek ("A Fast Sequential Decoding Algorithm Using a Stack", IBM J. Res. Dev., Vol.13, November 1969, pp. 675-685), respectively, is known. The present invention is applicable to a sequential decoder using both these algorithms.
In particular, error correction coding is used in the field of satellite communication because transmission length without a repeater is long and the power of the received signal is small in satellite communication.
(2) Description of the Related Art
FIG. 4 is a block diagram of a conventional sequential decoder receiving a pair of signal bits consisting of an information bit and a parity bit at one time and sequentially decoding each signal bit using the Fano algorithm.
In the field of satellite communication, quadrature phase shift keying is often used to modulate a signal to be transmitted. In the quadrature phase shift keying (QPSK), a pair of binary signals synchronized with each other are modulated as four phase states of the carrier wave, i. e., the pair of baseband signals (1,1) is modulated to the phase state .pi./4, the pair of baseband signals (0,1) is modulated to the phase state 3.pi./4, the pair of baseband signals (0,0) is modulated to the phase state -3.pi./4, and the pair of baseband signals (1,0) is modulated to the phase state .pi./4. On the receiver side, received signals are first demodulated to one of the above four pairs of baseband signals (1,1), (0,1), (0,0), and (1,0), and then are decoded in a sequential decoder.
When the transmitted signals are generated by the encoder as shown in FIG. 1, which generates a pair of coded signal bits consisting of an information bit and a parity bit as shown in FIG. 5, the above pair of the baseband signals may be the pair of output signals of the encoder. Therefore, the pair of input signals of the sequential decoder of FIG. 4 may be the QPSK output of the above demodulator.
In FIG. 4, reference numeral 1 denotes a buffer memory, 2 denotes a pointer, 4 denotes a path decision circuit, 5 denotes a search direction control circuit, 6 denotes a path memory, and 7 denotes an address counter.
The buffer memory 1 receives and stores received and demodulated (coded) data consisting of a pair of bits comprised of an information bit and a parity bit.
The path decision circuit 4 receives a pair of coded signals consisting of an information bit and a parity bit at one time from the buffer memory 1, internally generates a parity bit from decoded information bits by an internal encoder (not shown in FIG. 4) which is contained in the path decision circuit 4, calculates the branch metric, which is defined by Fano in the aforementioned publications, "Heuristic Discussion of Probabilistic Decoding", IEEE Transaction on Information Theory, Vol. IT-19, April 1963, pp.64-73, and the U.S. Pat. No. 3,457,562, for each information bit, which indicates a local likelihood for each possible branch for the information bit in the forward direction from each node corresponding to the information bit in the tree diagram as shown in FIG. 3. The path decision circuit also selects a local (at the node) most likely branch (path) based on the above-calculated branch metric, and outputs the decoded signal bits corresponding to the above-selected branch. The decoded signals are then written in the path memory 6.
The above branch metric obtained in the path decision circuit 4 is supplied to the search direction control circuit 5.
The search direction control circuit 5 accumulates branch metrics of the branches, each of which has been selected as a local most likely branch at each corresponding node on the selected path, to obtain the path metric, and holds the path metric. That is, the search direction control circuit 5 adds a branch metric in the forward direction which is newly received from the path decision circuit 4, to the path metric held in the search direction control circuit 5. Alternatively, the search direction control circuit or subtracts a branch metric in the backward direction which is calculated in the path decision circuit 4, from the path metric held in the search direction control circuit 5. The search direction control circuit 5 then determines the above direction of the search by comparing the above path metric with a predetermined threshold, and makes the path decision circuit 4 carry out the search operation in the determined direction by supplying a search direction control signal.
If the above path metric is larger than a threshold which is predetermined in accordance with the Fano algorithm, it is determined that the forward search of the local most likely branch can be continued. Or, if the above path metric is not larger than the threshold, it is determined that the preceding forward search at the preceding node, wherein the branch from the preceding node tothe above node was selected, was wrong, and the search operation must be restarted from the preceding node excluding the wrong branch.
According to the Fano algorithm, the path metric at each node is renewed when the operation is shifted from one node to the next, i. e., the path metric is not memorized at the timing of the operation at the next node. Therefore, when returning to the preceding node from the above wrong node, the branch metric from the wrong node to the preceding node must be calculated and the calculated branch metric is subtracted from the path metric at the wrong node to again obtain the path metric at the preceding node. This is the backward search process in accordance with the Fano algorithm.
The above operation by the path decision circuit 4 is a well-known procedure in accordance with the Fano algorithm. An example of the path search according to the Fano algorithm is shown in FIG. 6, wherein references a, b, c, . . . each denote a node.
Going back to FIG. 4, the path memory 6 receives and holds the output of the path decision circuit 4 by the above forward search, and outputs the previously held decoded values back to the path decision circuit 4 for use in the backward search
The address counter 7 outputs an address to both the buffer memory 1 and the path memory 6. A newly received bit of coded data is written in an address which is determined by the above address from the address, counter 7, and one bit of decoded data which has been held in an address which is also determined by the above address from the address counter 7 in the path memory 6, is read out.
The pointer 2 outputs the operating address of the path decision circuit 4, i. e., outputs the address of the node from which node a local most likely path (branch) is obtained by calculating branch metrics for all possible branches from the node in the forward or backward direction.
Furthermore, in the prior art, some of the parity bits are removed from the series of output bits of the encoder at a predetermined rate before being modulated on the sender side to increase the code rate, i. e., to increase transmission efficiency. This method is called the punctured method.
FIG. 7 shows an example of data generated by applying the punctured method to the output of the encoder which generates a pair of data including an information bit and a corresponding parity bit as shown in FIG. 5. In this example, parity bits except the 3n-th parity bits, P.sub.3, P.sub.6, . . . are removed from the series of FIG. 5. In addition, in FIG. 7, each (2n-1)-th bit and 2n-th bits are paired for QPSK modulation.
In the prior art, when the series of the punctured and paired signals (for example, having a form as in FIG. 7) are received through a demodulator at the receiver side, the form of the series of punctured and paired signals as shown in FIG. 7 are transformed back to the form as shown in FIG. 5 by inserting dummy bits in the positions where the parity bits were previously removed. The transformed series of paired signals are then decoded in the sequential decoder as shown in FIG. 4.
Generally, fast operation of the sequential decoder is required. However, by the construction of FIG. 4, only one information bit is decoded through one forward search operation. Further, by the above punctured method, the inserted dummy bits generally do not coincide with the corresponding correct parity bits. Therefore, the above insertion of dummy bits substantially increases the number of errors, and thus the backward search operation of the Fano algorithm is more frequently carried out. This further lowers the decoding speed.